package leetcode_1401_1500;

public class LeeCode_1419 {
    public static void main(String[] args) {
//        System.out.println(minNumberOfFrogs("croakcroak"));
//        System.out.println(minNumberOfFrogs("crcoakroak"));
//        System.out.println(minNumberOfFrogs("croakcrook"));
//        System.out.println(minNumberOfFrogs("ccrrooaakk"));
        System.out.println(minNumberOfFrogs("crroakcoak"));
    }
    private static int minNumberOfFrogs(String croakOfFrogs) {
        int[] tab = new int[26];
        int n = croakOfFrogs.length();
        tab['c' -'a'] = 1;
        tab['r' -'a'] = 2;
        tab['o' -'a'] = 3;
        tab[0] = 4;
        tab['k' -'a'] = -10;
        int[] dp = new int[5];
        int[] arr = new int[n];
        for (int j = 0; j < n; j++) {
            arr[j] = tab[croakOfFrogs.charAt(j) - 'a'];
            if (arr[j] == 0) {
                return -1;
            }
        }
        if (arr[0] != 1){
            return -1;
        }
        dp[0]++;
        int i = 1, ans = 1;
        while (i < n){
            if (arr[i] == -10){
                if (dp[0] > 0 && dp[1] > 0 && dp[2] > 0 && dp[3] > 0){
                    for (int j = 0; j < 4; j++) {
                        ans = Math.max(ans, dp[j]);
                        dp[j]--;
                    }
                }else {
                    return -1;
                }
            }else if (arr[i] > arr[i - 1]){
                if (arr[i] - arr[i - 1] == 1) {
                    dp[arr[i] - 1]++;
                }else {
                    if (arr[i - 1] == -10){
                        dp[arr[i] - 1]++;
                    }else {
                        dp[arr[i] - 1]++;
                        for (int j = 0; j < arr[i] - 1; j++) {
                            if (dp[j] < dp[arr[i] - 1]){
                                return -1;
                            }
                        }
                    }
                }
            }else if (arr[i] < arr[i - 1]){
                int val = arr[i];
                dp[val - 1]++;
                int c = dp[val - 1];
                for (int j = 0; j < val - 1; j++) {
                    if (dp[j] < c){
                        return -1;
                    }
                }
            }else {
                dp[arr[i] - 1]++;
                for (int j = 0; j < arr[i] - 1; j++) {
                    if (dp[j] < dp[arr[i] - 1]){
                        return -1;
                    }
                }
            }
            i++;
        }
        for (int k : dp) {
            if (k > 0) {
                return -1;
            }
        }
        return ans;
    }
}
